A neural algorithm for a fundamental computing problem

简介

论文地址
  相似搜索(similarity search)，比如确认数据库中相似的图片或互联网上相似的文档，是许多大规模信息检索系统面临的基本计算问题。该论文发现果蝇嗅觉神经回路使用一种不同于传统计算科学算法(locality-sensitive hashing)的方法来解决这个问题。果蝇的神经回路赋予相似的输入刺激以相似的神经活动模式，所以接触到相似的气味时，可以应用之前学习到的行为。果蝇的算法，使用了三种不同于传统方法的计算成分。作者展示了在一些基准数据库上，和传统方法相比，果蝇算法可以用于改善相似搜索的性能。作者受此启发，为近似相似搜索(approximate similarity search or nearest-neighbors search)这一基本机器学习问题提出了新的计算策略。该策略将输入映射到更高维的空间，输出是稀疏的，并且尽可能保留数据之间的相似性。

果蝇嗅觉神经回路

  果蝇的嗅觉回路对不同的气味赋予一个相应的标签(tag)，该标签对应于当某气味出现时被激活的神经元的集合。这个标签对于学习对不同气味所做出的不同的行为十分关键。举个例子，如果奖励(eg.,糖水)或者惩罚(eg.,电击)与某种气味相关联，对应的，这种气味就变得更有吸引力(果蝇会接近)或者变得更有排斥性。据我们所知，赋予气味的标签是稀疏的，对每一种气味，只有很小一部分接受到气味信息的神经元被激活;也是非重叠的，两种随机选择的气味的标签之间只共享很少的激活神经元，如果有的话，这样可以很轻易的区分开来不同的气味。
  每种气味的标签要经过三步计算得到。如图(A)所示。
  第一步包括从果蝇鼻子处的气味受体神经元(odorant receptor neurons,ORNs)到肾小球处投影神经元(projection neurons,PNs)的前向反馈连接。果蝇鼻子处有50种ORNs，每一种ORNs对不同的气味具有不同的敏感性和选择性。因此，每一种输入的气味都在一个50维空间有一个由50种ORN决定的坐标。对于每一种气味，五十种气味受体神经元放电速率的分布都是指数分布(每一种对不同气味的敏感性和选择性不一样)，其均值取决于气味浓度。对于投影神经元来说，移除了这种浓度依赖性。对于每种气味，50种投影神经元的放电速率是指数分布的，对于所有气味和气味浓度，均值接近一样。因此，算法的第一步本质上来讲是均值中心化。这一步十分重要，这样果蝇就不会将气味类型和气味强度混淆。(这一步可以看作是预处理)
  第二步是算法的主要的insight开始的地方，包括40倍的神经元数量扩增。50个PNs投影到2000个Kenyon cells(KCs)，由一个稀疏二值随机矩阵连接。每一个KC从大约六个随机选择的PNs处接收并对其放电速率求和。
  第三步包括一个赢者通吃(winner-take-all)回路，使用来自单个抑制神经元的强抑制反馈实现。因此，除了放电速率最高的5%的神经元，其他的KLs都被沉默。剩下的5%神经元的放电速率对应于输入气味的标签。

论文贡献

  从计算机科学的角度出发，作者把果蝇的嗅觉回路看作一个哈希函数，输入是某种气味，输出是对应的标签(tag)。虽然标签应该将不同的气味区分开来，但果蝇的优点更在于对相似的气味赋予相似的标签，如图B所示。这样，从一种气味学习到的条件反应就可以应用到相似的气味，或者学习过的气味的噪声版本。这让作者推测果蝇嗅觉回路产生的标签是局部敏感的(locallity-sensitive)，即越相似的一对气味，它们的标签也越相似。局部敏感哈希(LSH)是解决大规模相似搜索问题的基础。果蝇的算法，在三个方面不同于传统算法：使用稀疏二值随机矩阵将输入到更高维的输出，接着使用赢者通吃策略稀疏标签。
该论文有如下贡献:

1. 受果蝇算法的启发，提出了一种新类型的LSH算法，可以高效地寻找高维空间中一个点的近似最近邻。
2. 证明了果蝇算法构造的标签保留了输入的近邻结构，并比过去经常使用的算法计算上更高效。
3. 展示了果蝇的算法与传统LSH算法相比，在三个基准数据库上改善了寻求最近邻的性能。

最近邻搜索，LSH，果蝇算法的关系

最近邻搜索

  想象你有一张大象的照片，你想在互联网上超过百万的图片中，寻求到100张看起来和你的大象照片最相似的图片。这就被称为最近邻搜索问题，在信息检索，数据压缩，机器学习中具有根本重要性。每一张图片通常被表征为一个$d$维特征向量，两张图片（特征向量）的相似性使用距离来度量，目的是高效地得到任意查询的图片的最近邻。如果互联网只具有很少的图片，可使用暴力线性搜索轻易地找到精确的最近邻。如果互联网具有很多的图片，但每一张图片被表征为一个低维向量(eg.,10 or 20 features)，则可以使用空间划分方法，比如kd-trees，这样足够用了。但对于高维向量的大规模数据库，没有一种方法可行。

LSH

  幸运的是，在许多应用环境中，返回和查询数据足够接近的近似最近邻的集合，只要足够快，也是可行的。这样就推动了一种使用被称为LSH的概率技术来寻找近似最近邻的方法的产生。对于果蝇来说，一种气味的标签(hash)对应于KCs放电速率的特定向量。局部敏感特性显示两种相似的气味会被表征为相似的标签。同样，对于图片搜索来讲，一张大象图片的标签会与另一张大象图片的标签更相似，与摩天大楼照片的标签相比。形式上可定义为：

  传统的哈希函数(non-LSH)，将输入数据点随机均匀的分散到特定空间中；而LSH提供一种从$d$维空间到$m$维空间的保留距离的点嵌入方式。因此，在输入空间里越相似的两个点，就会以更高的概率被赋予相同或相似的标签；在输入空间里越不相似的两个点，被赋予的标签则越不相似。
  对于设计LSH函数，一个常见的trick是计算输入数据的随机投影，通常是将输入的特征向量和一个随机矩阵相乘。The Johnson-Lindenstrauss定理及其变体，为使用各种类型的随机投影，将点从$d$维空间投影到到$m$维空间，能多好保留局部性提供了强大的理论证明。
  引人注目的，果蝇也使用随机投影将标签分配给气味(step 2)，但和传统的LSH算法相比有三处不同。第一，果蝇算法使用稀疏二值随机投影，而LSH函数通常使用计算代价更高的密集投影，比如高斯随机投影。第二，果蝇算法将输入投影到更高维的空间，而传统的LSH则投影到更低维空间。第三，果蝇算法使用赢者通吃策略使输出稀疏化，而传统的LSH算法则保留输出的密集性。

Deriving the distance-preserving properties of the fly’s olfactory circuit

  我们可以将从PNs到KCs的映射看作是一个双向连接矩阵(m X d)，$x$是$d$维向量，代表输入，在果蝇那其中每一个$x_i$代表一个PN；$y$是$m$维向量，代表输出，$y$中每一个$y_i$则代表一个KC，每一$y_i$等于少数的$x_i$的和。二者之间的连接关系可以无向边连接表示。这个双向图可以使用一个m X d的邻接矩阵表示如下：

$$M_{ji} = \begin{cases} 1,&\text{if $x_i$ connects $y_i$ } \\ 0, &\text{otherwise} \end{cases}$$

这样就有：

$$y = Mx$$

在APl抑制反馈后，只有放电速率最大的$k$个KCs保留了它们的值，其余得都被归零了，这就是赢者通吃策略。这样可以产生一个$m$维的稀疏向量，也就是标签，如下所示：

$$z_i = \begin{cases} y_i ,&\text{if $y_i$ is one of the k largest entries in y } \\ 0, &\text{otherwise} \end{cases}$$

$M$的一种简单模型就是一个稀疏二值随机矩阵：每一个元素$M_{ij}$用概率$p$独立设置，即该元素为1的概率$p$。比如，选择$p = 6/d$，意味着$M$有大约6个1，这符合实验发现。、
  在补充部分，作者证明，果蝇算法的前两步产生的标签，符合预期的保留了输入气味的$L2$距离。证明如下：
定理 1:如果两个输入$x,x \in R^d$被分别投影到$y,y’ \in R^m$，我们有：

$$E{ \parallel y-y'\parallel}^2 \le mp((1-p){\parallel x-x'\parallel}^2)$$

  同样，作者证明当$m$足够大时，变量${\parallel y\parallel}^2$紧密的集中在其期望：

$$(1-\epsilon)E {\parallel y \parallel}^2 \le (1+\epsilon) E {\parallel y \parallel}^2$$

对于很小的$\epsilon >0$以一个很高的概率成立。

  因此结果就证明果蝇算法代表了LSH新的一种类型。(ps:这里只有结论，原论文也没有证明部分，应该看看LSH算法证明来理解这里)

讨论

  总的来说，作者确定了一种新的大脑算法，该算法支持重要的感官功能，从理论上证明了其距离保留的性质。作者亦在三种基准数据库上经验的评估了该算法用于寻找最近邻的表现。这份工作提供了大脑中相似性匹配策略和大规模信息检索系统中最近邻搜索的协同作用。该论文的工作可以应用在重复值检测，聚类和 energy-efficient deep learning。
  对LSH，有许多扩展，比如使用多个哈希表来提高精度；使用多探头(multi-probe)，这样相似的标签就会落入同一个桶中；各种用于离散散列的量化技巧。也有方法可以加速随机投影乘法，比如对于LSH，可使用 fast Johnson-Lindenstrauss transforms；对于果蝇算法，可以使用 fast sparese matrix multiplication。
  接下来，我们将注意力放在数据无关哈希上，也就是哈希函数不是从之前的数据学习来的，也没有使用先前的数据。最近，许多类型的数据无关的LSH被提出来，包括 PCA hashing， spectral hashing ， semantic hasing，deep hashing和其他的。果蝇算法的一些部分之前也有被人使用。比如 MinHash和winer-take-all hash都使用了类似赢者通吃的策略，但没有一种扩展了数据维度。同样的，随机映射也被多种方法使用，但没有一种使用稀疏二值随机映射。

思考

  该论文确实为解决一个根本问题—相似搜索，提供了新的方法。因为相似搜索在很多地方都可以用到，比如，聚类，最近邻，信息检索。而果蝇算法之所以计算成本更低，我的理解是随机映射使用的稀疏二值矩阵，虽然被扩展到更高维，但计算量实际上很小。
  果蝇算法使用的哈希函数是数据无关的，因为是以概率$p$随机生成的。nips2018的一篇论文对此做了改进，$M$使用数据训练得到。